1. Technical Field
The present invention relates in general to a distributed flow control system and method for General Packet Radio Service (GPRS) networks and in particular to a system and method for adapting a leaky bucket mechanism to a system having multiple traffic sources wherein the combined traffic from all sources must satisfy a single set of peak and average rate requirements.
2. Description of the Related Art
Wireless communication technologies require the use of various defined standards such as for voice and data communications. General Packet Radio Service (GPRS) is a relatively newer version standard that has been established for wireless data communications in Europe, and GPRS is able to be used anywhere in the world. A general prior art diagram of the topology of a GPRS network 10 is shown in FIG. 1. The GPRS network 10 generally comprises a number of nodes. The GPRS network 10 comprises a mobile switching center (MSC), a visitor location register (VLR) 12, a home location register (HLR), an authentication center (AuC) 14, a gateway GPRS support node (GGSN) 20, a serving GPRS support node (SGSN) 24, a base station system (BSS) having an antenna 30, and a packet control unit (PCU) 28. The MSC/VLR provides voice communications for wireless or cellular telephones. The MSC/VLR 12 is in direct communications with the HLR/AuC 14, the SGSN 24, and the BSS/PCU 28. The HLR/AuC 14 is in direct communications with SGSN 24 and GGSN 20.
The GPRS network 10 is configured to support interfaces to and from outside packet data networks. FIG. 1 shows that the GGSN 20 is coupled to and in communications with outside packet data networks that support the internet protocol (IP) 16 or the X.25 protocol 18. In FIG. 1, data packets come in from the outside network (i.e. IP 16 or X.25 networks 18) to the GGSN 20, then to the SGSN 24, and then to the BSS/PCU 28. Thus, two way communications exist between the BSS/PCU 28 and the SGSN 24, the GGSN 20, and the outside network(s). One problem that exists for the data packet coming from the GGSN 20 (or outside) to the SGSN 24 and then to the BSS/PCU 28 is that the packet control unit (PCU) may have limited memory space. A long queue of incoming data may exist at the PCU, and the PCU may not be able to receive anymore data or information from the SGSN 24. Therefore, a method for regulating traffic flow from the SGSN to the PCU is necessary.
FIG. 4 is a prior art block diagram of the protocol stack 55 between the BSS/PCU stack 56 for the BSS/PCU 28 and the SGSN stack 66 for the SGSN 24 in a GPRS network 10. The BSS/PCU stack 56 comprises a relay 58, a Base Station System GPRS protocol (BSSGP) layer 60, a frame relay layer 62, and a physical layer 64. The SGSN stack 66 comprises a relay 66, a SNDCP layer 70, a Logical Link Control (LLC) layer 72, a BSSGP layer 74, a frame relay layer 76, and a physical layer 78. According to the GPRS standards, a frame relay network 63 couples the BSS/PCU 28 to the SGSN 24. In the BSS/PCU stack 56, BSSGP layer 60 is located immediately above the frame relay layer 62. The operations of the BSSGP layer 60 include flow control and transmission of LLC frame 39 or data packet frame related information, such as routing and QoS requirements, between the SGSN 24 and the BSS/PCU 28. The data streams transmitted from the SGSN 24 to a cell is grouped together to form a BSSGP virtual circuit (BVC). Flow control between the SGSN 24 and the BSS/PCU 28 is performed both on per BVC and per mobile station basis.
FIG. 2 shows a prior art diagram of the flow control between the SGSN 24 and the BSS/PCU 28. Flow control parameters 32 are programmed and established from the BSS/PCU 28. These flow control parameters 32 are directed from the BSS/PCU 28 to the SGSN 24 to control and regulate the flow of data from the SGSN 24 to the BSS/PCU 28. Thus, regulated data flow exists from the SGSN 24 to the BSS/PCU 28. The flow control mechanism implemented at the SGSN 24 is based on a leaky bucket flow control mechanism. The flow control parameters established by the BSS/PCU 28 are used to dimension the leaky bucket mechanism implemented at the SGSN 24.
The leaky bucket flow control mechanism is a simple and effective system and method for regulating and controlling traffic flow. Each leaky bucket is dimensioned by two parameters: leak rate (R) and bucket size (maximum bucket size Bmax). These parameters together control the peak and the average rates of traffic departure from a traffic source. The leaky bucket flow control mechanism regulates the output bandwidth allocation to a traffic source such that traffic departing from the controlled source does not exceed the specified mean and peak rate values. The basic concept of this mechanism is to associate a bucket 40 with a traffic source at the SGSN 24 (see FIG. 3). The bucket 40 has a finite number of bytes in size (i.e. maximum bucket size Bmax). When the traffic source at the SGSN 24 transmits traffic to the output link 80, an equivalent number of bytes must be put into the bucket 40. If the bucket 40 is full, transmission is not allowed. The available data 39 is either queued in the buffer 38 or discarded. Consequently, the traffic source at the SGSN 24 is not able to transmit more data 39 than the available capacity of the bucket 40. At the same time, the bucket 40 xe2x80x9cleaksxe2x80x9d(i.e. the bucket level drops) at a given leak rate R such that the data departure is not totally confined to the finite bucket size. Based on the leaky bucket mechanism, the mean departure rate of the traffic source at the SGSN 24 cannot exceed the bucket leak rate R. At any time instant, the traffic source at the SGSN 24 is not able to send out more data 39 than the bucket size Bmax.
An application of the leaky bucket flow control mechanism 36 (see FIG. 3) is found in GPRS as specified in the European Telecommunications Standards Institute (ETSI) Global System for Mobile Communications (GSM) phase 2+ standards [1]. GPRS is the packet data extension of the circuit based GSM wireless communication standard. Details and applications of these standards and specifications are disclosed in ETSI, xe2x80x9cDigital Cellular Telecommunications System (phase 2+); General Packet Radio Service (GPRS); Service Description; Stage 2,xe2x80x9d ETSI GSM 03.60, Version 6.1.1, August 1998. These standards, specifications, and publications are incorporated by reference herein. Referring to FIG. 1 and as stated earlier, the GGSN node 20 is the interface between the GPRS network and the outside networks 16 or 18. The GGSN 20 is responsible for forwarding data packets to the appropriate SGSN 24 and to provide mobility, security, and billing related operations. The SGSN 24 is responsible for the buffering and delivery of packet data and the handling of GPRS related signaling messages for subscribers residing in its assigned area. Each SGSN 24 is connected to one or more BSS/PCU 28. The BSS/PCU 28 is responsible for interfacing with the mobile station or terminal 27 with antenna 29 through the GPRS air interface protocol.
FIG. 3 shows a prior art diagram of the leaky bucket flow control mechanism 36. As a logical link control (LLC) frame of data 39 is forwarded from the data buffer 38 of the SGSN 24 to the BSS/PCU 28 via a BSSGP virtual circuit. A number of bytes equal to the length of the LLC frame must be placed in the bucket 40. In other words, the same amount of data 39 that has been forwarded from the SGSN 24 to the BSS/PCU 28 needs to be placed into the bucket 40. The data 39 collected in the bucket 40 leaks at the leak rate (R) 45. The data 39 leaking from the bucket 40 operates to control the rate of data flow from the SGSN 24 to the BSS/PCU 28 by requiring that a sufficient amount of space (equal to the size of the next LLC frame to be transmitted) in the leaky bucket 40 needs to exist before the SGSN 24 can further send data to the BSS/PCU 28. The level of the bucket 40 needs to drop (i.e. xe2x80x9cleakxe2x80x9d) below some level or amount before a next LLC frame 39 or data packet can be sent from the SGSN 24 to the BSS/PCU 28. If the bucket 40 is full or would overflow if a next LLC frame 39 is sent, then the next LLC frame 39 is delayed. In other words, a next LLC frame 39 or data frame is forwarded from the SGSN 24 to the BSS/PCU 28 via a BSSGP virtual circuit only if the length (L) of the next LLC frame 39 is less than or equal to the difference between the maximum bucket size (Bmax) 43 and the current bucket level (Bcur) 47, or otherwise, the next LLC frame 39 is delayed.
According to the GPRS standards, the leaky bucket flow control mechanism 36 is used to regulate traffic flow through a BVC from the SGSN 24 to the BSS/PCU 28. A feedback control scheme is then employed to set up the parameters of the leaky bucket at the SGSN 24. According to this method, each BSS/PCU 28 periodically sends to the SGSN 24 the leaky bucket parameter for each BVC supported by the BSS/PCU 28. The leaky bucket parameters include the maximum bucket size and the leak rate, which are determined based on the current congestion condition at the BSS/PCU 28 and the behavior of the air channels. The leaky bucket mechanism implemented at the SGSN 24 then controls the departing traffic of the BVC based on these parameters. FIG. 3 shows various components involved in the BVC flow control.
A main problem arises when multiple sources belonging to the same BVC exist at the SGSN side of the GPRS network 10. The difficulty arises when the leaky bucket flow control mechanism 36 is adapted to the situation where multiple sources exist at the SGSN side of the GPRS network 10. For example, a distributed network architecture 37 is shown in FIG. 5. The distributed network architecture 37 shows data transferred between a SGSN 24 having within it multiple source servers (i.e. server142, server244, . . . servern 46) in communication with routers or routing boxes (i.e. router 148 . . . router k 50). The routers, in turn, are in communication with the frame relay 26 wherein the frame relay 26 is a public data network (which is similar to the Internet network). The frame relay 26, in turn, is in communication with the single destination BSS/PCU 28. FIG. 5 shows the problem from the configuration where the multiple sources are multiple routers within the SGSN 24. However, the problem is not limited to multiple sources that are multiple routers. The multiple sources may be multiple source servers, multiple SGSNs 24, and/or any other type(s) of multiple source(s) in any systems other than GPRS.
In other words, the setup in FIG. 5 is where a BVC is split across at multiple hardware interface cards or multiple SGSNs 24. The setup for this type of hardware/network architecture is preferable since it achieves higher reliability and enhances nodal or network capacity. Thus, it is necessary to ensure that the total traffic entering the BVC from all interface cards or SGSNs 24 adhere to the leaky bucket parameters as provided by the BSS/PCU 28.
One simple solution would be to implement a leaky bucket mechanism 36 at each BVC terminating point. However, since the BSS/PCU 28 is limited to providing only one set of leaky bucket parameters for controlling data flow, the issue becomes how to dimension all of the leaky buckets 36 using only one set of parameters to provide flow control of data. Therefore, a first simple solution to the multiple leaky bucket dimensioning problem is to dimension all of the leaky buckets to the same set of parameters, that is, dimension all leaky buckets using the same bucket size and leak rate. A second solution would be to have the leak rate divided among all of the leaky buckets and use the same bucket size for all leaky buckets. A third solution would be to have the bucket size divided among all leaky buckets and use the same leak rate for all leaky buckets. However, all of these solutions or attempted solutions either fail to enforce the required peak and average rates (i.e. first solution failure) or are overly restrictive such that the allowable peak and average rates cannot be achieved (i.e. second and third solutions failures).
Another solution for ensuring peak and average rates would be to provide a centralized leaky bucket mechanism that regulates the data traffic from all of the individual routers. The centralized leaky bucket mechanism would be provided by adding another box or hardware that collects data from all of the individual routers. However, the adding of an additional box or hardware is not desired due to space, cost, and other such issues that arise from utilizing additional hardware.
It would therefore be advantageous and desirable to provide a distributed flow control system and method for GPRS networks to control and regulate data flow between multiple sources exist at the SGSN side of the GPRS network and a single destination at the BSS/PCU side of the GPRS network. It would also be advantageous and desirable to provide such a distributed flow control system and method for GPRS networks to ensure the total departing traffic from all of the sources conforms to the peak and average rate requirements that have been set forth by the BSS/PCU. It would further be advantageous and desirable to provide such a distributed flow control system and method for GPRS networks that dimension all of the leaky bucket mechanisms using only one set of parameters to provide flow control of data traffic. It would still further be advantageous and desirable to provide such a distributed flow control system and method for GPRS networks that avoids using an additional box or hardware for being able to implement the leaky bucket flow control mechanism when multiple sources exist at the SGSN side of the GPRS network.
It is therefore one object of the present invention to provide a distributed flow control system and method for GPRS networks to control and regulate data flow between multiple sources exist at the SGSN side of the GPRS network and a single destination at the BSS/PCU side of the GPRS network.
It is another object of the present invention to provide such a distributed flow control system and method for GPRS networks to ensure the total departing traffic from all of the sources conforms to the peak and average rate requirements that have been set forth by the BSS/PCU.
It is a further object of the present invention to provide such a distributed flow control system and method for GPRS networks that dimension and factor all of the leaky bucket mechanisms using only one set of parameters to provide flow control of data.
It is still a further object of the present invention to provide such a distributed flow control system and method for GPRS networks that avoids using an additional box or hardware for being able to implement the leaky bucket flow control mechanism when multiple sources exist at the SGSN side of the GPRS network.
The foregoing objects are achieved as is now described. A distributed flow control system and method for GPRS networks to control and regulate data flow between multiple sources and a single destination within a GPRS network. The present system and method ensures the departing traffic from all of the sources conforms to the peak and average rate requirements that have been set forth by the BSS/PCU. A leaky bucket flow control mechanism is used at each respective one of the multiple sources for controlling flow of data from each respective source to the single destination. A maximum bucket size of a leaky bucket and a bucket leak rate are defined for each leaky bucket flow control mechanism. A multiplier (L) is estimated and determined for each respective source based on recent data arrival behaviors of the multiple sources. When a frame of the data is sent from the respective source to the single destination, a number of bytes equal to the size of the transmitted frame times the multiplier L is added to the leaky bucket. An additional frame of data is allowed to be sent from the respective source to the single destination if transmission of the data frame will not result in overflow of the leaky bucket. An additional frame of data is prohibited from being sent from the respective source to the single destination when transmission of the data frame will result in the overflow of the leaky bucket.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.